#ifndef QUICKSORT_H
#define QUICKSORT_H

#include <time.h>

template <typename T>
int Partion(T seq[],int p,int r)
{
    T key=seq[r];
    int i=p-1;
    for(int j=p;j<r;j++)
    {
        if(seq[j]<=key)
        {
            i++;
            T temp=seq[i];
            seq[i]=seq[j];
            seq[j]=temp;
        }
    }
    T temp=seq[i+1];
    seq[i+1]=seq[r];
    seq[r]=temp;
    return i+1;
}

template <typename T>
int RandPartion(T seq[],int p,int r)
{
    srand((unsigned int)time(NULL));
    int rd=p+rand()%(r-p+1);
    T temp=seq[rd];
    seq[rd]=seq[r];
    seq[r]=temp;
    return Partion(seq,p,r);
}

template <typename T>
void QuickSort(T seq[],int p,int r)
{
    if(p<r)
    {
        int q=RandPartion(seq,p,r);
        QuickSort(seq,p,q-1);
        QuickSort(seq,q+1,r);
    }
}

template <typename T>
T nth_select(T seq[],int p,int r,int i)
{
    if(p==r)
        return seq[p];
    if(p<r)
    {
        int q=RandPartion(seq,p,r);
        int k=q-p+1;
        if(i==k)
            return seq[q];
        else if(i<k)
            return nth_select(seq,p,q-1,i);
        else
            return nth_select(seq,q+1,r,i-k);
    }
}

template <typename T>
T find_median(T seq1[],T seq2[],int n,int low,int high)
{
    if(low>high)
        return (T)-999999;
    int k=(low+high)/2;
    if(k==n-1 && seq1[n-1]<=seq2[0])
        return seq1[n-1];
    else if(k<n-1 && seq1[k]>=seq2[n-k-1] && seq1[k]<=seq2[n-k])
        return seq1[k];
    else if(seq1[k]>seq2[n-k])
        return find_median(seq1,seq2,n,low,k-1);
    else
        return find_median(seq1,seq2,n,k+1,high);
}

template <typename T>
T two_array_median(T seq1[],T seq2[],int n)
{
    T median=find_median(seq1,seq2,n,0,n-1);
    if(median==(T)-999999)
        return find_median(seq2,seq1,n,0,n-1);
    else
        return median;
}

#endif